package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/study/live/716/7/3?autoplay=1">
 * 第3节 随堂习题-字典树的实现</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * <p>
 * 字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。
 * <p>
 * 假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。
 * <ol>
 *      <li>void insert(String word)：添加word，可重复添加；</li>
 *      <li>void delete(String word)：删除word，如果word添加过多次，仅删除一次；</li>
 *      <li>boolean search(String word)：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；</li>
 *      <li>int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量。</li>
 * </ol>
 * 现在给定一个m，表示有m次操作，每次操作都为以上四种操作之一。每次操作会给定一个整数op和一个字符串word，op代表一个操作码，如果op为1，则代表添加word，op为2则代表删除word，op为3则代表查询word是否在字典树中，op为4代表返回以word为前缀的单词数量（数据保证不会删除不存在的word）。
 * <p>
 * 对于每次操作，如果op为3时，如果word在字典树中，请输出“YES”，否则输出“NO”；如果op为4时，请输出返回以word为前缀的单词数量，其它情况不输出。
 * 示例1
 * 输入
 * [["1","qwer"],["1","qwe"],["3","qwer"],["4","q"],["2","qwer"],["3","qwer"],["4","q"]]
 * 输出
 * ["YES","2","NO","1"]
 * <p>
 * 备注:
 * <li>m <= 10^5</li>
 * <li>|word| <= 20</li>
 *
 * @author or2
 * @date 2021年09月28日 时间: 8:30
 */
public class TrieTree {

    private static class TrieNode {
        private int path;
        private int end;
        private TrieNode[] next;

        public TrieNode() {
            this.path = 1;
            this.end = 0;
            this.next = new TrieNode[26];
        }
    }

    private TrieNode root;

    public TrieTree() {
        this.root = new TrieNode();
    }

    /**
     * 添加word，可重复添加
     *
     * @param word 添加的单词
     */
    public void insert(String word) {
        char[] word2Chars = word.toCharArray();
        /*迭代处理每一个字符*/
        TrieNode pointer = root;
        for (int i = 0; i < word2Chars.length; i++) {
            int offset = word2Chars[i] - 'a';
            if (pointer.next[offset] == null)
                pointer.next[offset] = new TrieNode();
            else
                pointer.next[offset].path++;
            pointer = pointer.next[offset];
        }
        pointer.end++;
    }

    /**
     * 查询word是否在字典树中出现过(完整的出现过，前缀式不算)
     * @param word 被查找的单词
     * @return 是否在该字典树中出现过
     */
    public boolean search(String word) {
        char[] word2Chars = word.toCharArray();
        TrieNode pointer = root;
        for (int i = 0; i < word2Chars.length; i++) {
            int offset = word2Chars[i] - 'a';
            if (pointer.next[offset] == null)
                return false;
            else
                pointer = pointer.next[offset];
        }
        return pointer.end > 0;
    }

    public void delete(String word) {
        if (!search(word))
            return;
        char[] word2Chars = word.toCharArray();
        TrieNode pointer = root;
        for (int i = 0; i < word2Chars.length; i++) {
            int offset = word2Chars[i] - 'a';
            /*如果路径无效, 直接删除掉*/
            if (pointer.next[offset].path==1) {
                pointer.next[offset] = null;
                return;
            } else
                pointer.next[offset].path--;
            pointer = pointer.next[offset];
        }
        pointer.end--;
    }

    public int prefixNumber(String word) {
        char[] word2Chars = word.toCharArray();
        TrieNode pointer = root;
        for (int i = 0; i < word2Chars.length; i++) {
            int offset = word2Chars[i] - 'a';
            if (pointer.next[offset]==null)
                return 0;
            pointer = pointer.next[offset];
        }
        return pointer.path;
    }
}
